package leetcode每日一题;

/**
 *
 */
@SuppressWarnings("all")
public class 斐波那契数 {
    public static void main(String[] args) {
        System.out.println(fib2(0));
    }

    /**
     * 递归实现   效率低，因为存在重复计算
     */
    public static int fib1(int n) {
        if(n == 0) {return 0;}
        if(n == 1) {return 1;}
        return fib1(n-1) + fib1(n-2);
    }

    /**
     * 公式法
     * 由于斐波那契序列有地推公式 f[i] = f[i-1] + f[i-2]  i >= 2
     * f[0] = 0 f[1] = 1,考虑特征方程 x^2 + x + 1 = 0 ,有判别法可知有两个跟
     * 分别为  貌似结果部分正确，部分不正确
     */
    public static int fib2(int n) {
        return (int) ((Math.sqrt(5)/5) * Math.pow((1+Math.sqrt(5))/2,n) - (Math.sqrt(5)/5) * Math.pow((1-Math.sqrt(5))/5,n));
    }

    /**
     * 动态规划
     * @param n
     * @return
     */
    public static int fib3(int n) {
        if(n <= 1) {return n;}
        int[] dp = new int[n+1];
        dp[0] = 0; dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}
